from collections import deque

def solve_maze_all_items(maze, coin_value=5, trap_penalty=-3, boss_penalty=-1, locker_penalty=-7):
    """
    处理所有物品的动态规划解法：金币(G)、陷阱(T)、BOSS(B)、机关(L)
    所有物品都只在第一次接触时产生效果
    
    参数:
    - maze: 迷宫矩阵
    - coin_value: 金币价值 (默认+5)
    - trap_penalty: 陷阱惩罚 (默认-3)
    - boss_penalty: BOSS惩罚 (默认-1)
    - locker_penalty: 机关惩罚 (默认-7)
    """
    rows = len(maze)
    cols = len(maze[0])
    
    # 收集所有关键位置
    start = None
    end = None
    items = []  # 统一存储所有可交互物品
    item_types = {}  # 记录每个物品的类型
    item_values = {}  # 记录每个物品的价值
    
    for i in range(rows):
        for j in range(cols):
            if maze[i][j] == 'S':
                start = (i, j)
            elif maze[i][j] == 'E':
                end = (i, j)
            elif maze[i][j] == 'G':  # 金币
                items.append((i, j))
                item_types[(i, j)] = 'coin'
                item_values[(i, j)] = coin_value
            elif maze[i][j] == 'T':  # 陷阱
                items.append((i, j))
                item_types[(i, j)] = 'trap'
                item_values[(i, j)] = trap_penalty
            elif maze[i][j] == 'B':  # BOSS
                items.append((i, j))
                item_types[(i, j)] = 'boss'
                item_values[(i, j)] = boss_penalty
            elif maze[i][j] == 'L':  # 机关
                items.append((i, j))
                item_types[(i, j)] = 'locker'
                item_values[(i, j)] = locker_penalty
    
    item_map = {item: idx for idx, item in enumerate(items)}
    num_items = len(items)
    
    # 统计各类物品数量
    coin_count = sum(1 for t in item_types.values() if t == 'coin')
    trap_count = sum(1 for t in item_types.values() if t == 'trap')
    boss_count = sum(1 for t in item_types.values() if t == 'boss')
    locker_count = sum(1 for t in item_types.values() if t == 'locker')
    
    print(f"迷宫物品统计:")
    print(f"  金币(G): {coin_count}个, 每个+{coin_value}")
    print(f"  陷阱(T): {trap_count}个, 每个{trap_penalty}")
    print(f"  BOSS(B): {boss_count}个, 每个{boss_penalty}")
    print(f"  机关(L): {locker_count}个, 每个{locker_penalty}")
    print(f"  总物品数: {num_items}")
    
    # 状态：(位置, 物品状态掩码)
    dp = {}
    parent = {}
    
    queue = deque([(start, 0, 0)])  # (位置, 状态掩码, 当前价值)
    dp[(start[0], start[1], 0)] = 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    max_value_at_end = float('-inf')
    best_end_state = None
    
    step_count = 0
    max_steps = 100000  # 防止无限循环
    
    while queue:
        step_count += 1
        (x, y), item_mask, current_value = queue.popleft()
        
        # 到达终点
        if (x, y) == end:
            if current_value > max_value_at_end:
                max_value_at_end = current_value
                best_end_state = (x, y, item_mask)
        
        # 探索四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 检查边界和墙壁
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] != '#':
                new_mask = item_mask
                new_value = current_value
                
                # 检查是否是可交互物品
                if (nx, ny) in item_map:
                    item_idx = item_map[(nx, ny)]
                    if not (item_mask & (1 << item_idx)):  # 第一次接触
                        new_mask |= (1 << item_idx)
                        new_value += item_values[(nx, ny)]
                
                # 更新状态
                state = (nx, ny, new_mask)
                if state not in dp or dp[state] < new_value:
                    dp[state] = new_value
                    parent[state] = (x, y, item_mask)
                    queue.append(((nx, ny), new_mask, new_value))
    
    print(f"搜索完成，共执行 {step_count} 步")
    
    # 回溯路径
    if best_end_state:
        path = []
        current = best_end_state
        while current in parent:
            path.append((current[0], current[1]))
            current = parent[current]
        path.append(start)
        path.reverse()
        
        # 分析路径收益
        analyze_detailed_path(path, maze, items, item_types, item_values)
        
        return max_value_at_end, path
    
    return float('-inf'), []

def analyze_detailed_path(path, maze, items, item_types, item_values):
    """详细分析路径中的收益"""
    total_gains = {'coin': 0, 'trap': 0, 'boss': 0, 'locker': 0}
    item_counts = {'coin': 0, 'trap': 0, 'boss': 0, 'locker': 0}
    collected_items = set()
    
    print("\n=== 详细路径分析 ===")
    
    for i, (x, y) in enumerate(path):
        if (x, y) in item_types and (x, y) not in collected_items:
            collected_items.add((x, y))
            item_type = item_types[(x, y)]
            item_value = item_values[(x, y)]
            
            item_counts[item_type] += 1
            total_gains[item_type] += item_value
            
            type_name = {
                'coin': '金币',
                'trap': '陷阱', 
                'boss': 'BOSS',
                'locker': '机关'
            }[item_type]
            
            sign = '+' if item_value >= 0 else ''
            print(f"步骤 {i:2d}: 在({x:2d},{y:2d}) 触发{type_name} {sign}{item_value}")
    
    print(f"\n=== 收益汇总 ===")
    total_value = 0
    for item_type, count in item_counts.items():
        if count > 0:
            type_name = {'coin': '金币', 'trap': '陷阱', 'boss': 'BOSS', 'locker': '机关'}[item_type]
            gain = total_gains[item_type]
            avg_value = gain / count if count > 0 else 0
            print(f"{type_name}: {count}个, 总计{gain:+d} (平均{avg_value:+.1f}/个)")
            total_value += gain
    
    print(f"\n最终总收益: {total_value}")
    
    # 策略建议
    print(f"\n=== 策略分析 ===")
    if item_counts['locker'] > 0:
        print(f"⚠️  触发了{item_counts['locker']}个机关，损失{abs(total_gains['locker'])}分")
    if item_counts['boss'] > 0:
        print(f"⚔️  遭遇了{item_counts['boss']}个BOSS，损失{abs(total_gains['boss'])}分") 
    if item_counts['trap'] > 0:
        print(f"🕳️  踩了{item_counts['trap']}个陷阱，损失{abs(total_gains['trap'])}分")
    if item_counts['coin'] > 0:
        print(f"💰 收集了{item_counts['coin']}个金币，获得{total_gains['coin']}分")

def visualize_maze_with_path(maze, path):
    """可视化迷宫和路径"""
    import copy
    visual_maze = copy.deepcopy(maze)
    
    # 标记路径（不覆盖特殊符号）
    path_positions = set(path)
    
    for i, (x, y) in enumerate(path):
        if visual_maze[x][y] == ' ':
            visual_maze[x][y] = '●'  # 路径标记
    
    print("\n=== 迷宫路径可视化 ===")
    print("图例:")
    print("  S=起点   E=终点   G=金币(+5)   T=陷阱(-3)")
    print("  B=BOSS(-1)   L=机关(-7)   ●=路径   #=墙壁")
    print()
    
    for i, row in enumerate(visual_maze):
        row_display = []
        for j, cell in enumerate(row):
            if (i, j) in path_positions and cell != ' ':
                # 如果路径经过特殊位置，用颜色标记
                row_display.append(f"[{cell}]")
            else:
                row_display.append(f" {cell} ")
        print(''.join(row_display))

# 增强版本：考虑路径长度的权衡
def solve_maze_with_step_cost(maze, coin_value=5, trap_penalty=-3, boss_penalty=-1, 
                             locker_penalty=-7, step_cost=0):
    """
    考虑步数成本的版本
    每走一步都有成本，鼓励找到更短的路径
    """
    # 基本逻辑与上面相同，但在状态转移时减去step_cost
    # 这里简化实现，只展示关键修改点
    
    rows = len(maze)
    cols = len(maze[0])
    
    # ... 前面的初始化代码相同 ...
    
    # 在状态转移时加入步数成本
    # new_value = current_value + item_values.get((nx, ny), 0) - step_cost
    
    print(f"使用步数成本: 每步 {step_cost}")
    return solve_maze_all_items(maze, coin_value, trap_penalty, boss_penalty, locker_penalty)

# 测试函数
if __name__ == "__main__":
    maze = [
    ["#","E","#","#","#","#","#","#","#","#","#","#","#","#","#"],
    ["#"," "," ","B"," "," "," "," "," "," ","#"," "," "," ","#"],
    ["#","#","#"," ","#"," ","#","#","#","#","#","#","#"," ","#"],
    ["#"," "," ","T","#"," "," ","G"," "," ","#"," "," "," ","#"],
    ["#"," ","#","#","#"," ","#","#","#","#","#","#","#"," ","#"],
    ["#"," "," "," ","#"," "," "," ","#"," ","#"," "," "," ","#"],
    ["#","#","#"," ","#"," ","#"," ","#"," ","#","#","#"," ","#"],
    ["#"," "," "," ","#"," ","#"," "," "," "," "," ","#"," ","#"],
    ["#","#","#","#","#"," ","#","#","#","#","#","L","#"," ","#"],
    ["#"," ","#","G","#"," "," ","G","#"," ","#"," "," "," ","#"],
    ["#"," ","#"," ","#"," ","#"," ","#"," ","#"," ","#","#","#"],
    ["#"," ","#"," ","#"," ","#","T"," "," ","#"," "," "," ","#"],
    ["#"," ","#"," ","#"," ","#","#","#"," ","#"," ","#","#","#"],
    ["#"," "," "," "," ","T"," "," ","#"," ","#"," "," "," ","#"],
    ["#","#","#","#","#","#","#","#","#","#","#","#","#","S","#"]
  ]
    
    print("=== 包含所有物品类型的迷宫求解 ===")
    max_value, path = solve_maze_all_items(
        maze, 
        coin_value=5, 
        trap_penalty=-3, 
        boss_penalty=-1, 
        locker_penalty=-7
    )
    
    print(f"\n🎯 最优解: {max_value} 分")
    print(f"📏 路径长度: {len(path)} 步")
    
    if path:
        print(path)